public class MyBinaryTree {
    public int postIdx = 0;
    public int searchIdx(int[] inorder, int left, int right, int val) {
        for (int i = left; i <= right; i++) {
            if (inorder[i] == val) {
                return i;
            }
        }
        return -1;
    }
    public TreeNode creatTree(int[] inorder, int[] postorder, int left, int right) {
        if (left > right) return null;

        TreeNode root = new TreeNode(postorder[postIdx]);
        int inIdx = searchIdx(inorder,left,right,root.val);
        postIdx--;

        root.right = creatTree(inorder,postorder,inIdx+1,right);
        root.left = creatTree(inorder,postorder,left,inIdx-1);

        return root;
    }
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        postIdx = postorder.length - 1;
        return creatTree(inorder,postorder,0,postIdx);
    }
    public static TreeNode prev = null;
    public static TreeNode creatList(TreeNode root) {
        if (root == null) return null;

        creatList(root.left);
        root.left = prev;
        if (prev != null) {
            prev.right = root;
        }
        prev = root;
        creatList(root.right);

        return root;
    }
    public static TreeNode Convert(TreeNode pRootOfTree) {
        TreeNode head = creatList(pRootOfTree);
        while (head != null && head.left != null) {
            head = head.left;
        }
        return head;
    }

    public static void quickSort(int[] arr, int left, int right) {
        if (left >= right) return;
        int i = left - 1, j = right + 1, x = arr[i + j >>> 1];
        while (i < j) {
            do i++; while (arr[i] < x);
            do j--; while (arr[j] > x);
            if (i < j) {
                int t = arr[i];
                arr[i] = arr[j];
                arr[j] = t;
            }
        }
        quickSort(arr,left,j);
        quickSort(arr,j+1,right);
    }

    public static void main(String[] args) {
        int[] arr = {1,2,5,3,4};
        quickSort(arr,0,arr.length-1);
        System.out.println(arr);
    }
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) return null;
        if (root == p) return p;
        if (root == q) return q;

        TreeNode left = lowestCommonAncestor(root.left,p,q);
        TreeNode right = lowestCommonAncestor(root.right,p,q);

        if (left != null && right != null) return root;
        if (left != null) return left;
        return right;
    }

    public static TreeNode creatTreeNode() {
        TreeNode a = new TreeNode(10);
        TreeNode b = new TreeNode(6);
        TreeNode c = new TreeNode(14);
        TreeNode d = new TreeNode(4);
        TreeNode e = new TreeNode(8);
        TreeNode f = new TreeNode(12);
        TreeNode g = new TreeNode(16);
        a.left = b;
        a.right = c;
        b.left = d;
        b.right = e;
        c.left = f;
        c.right = g;
        return a;
    }

    public static ListNode creatList() {
        ListNode a = new ListNode(4);
        ListNode b = new ListNode(2);
        ListNode c = new ListNode(1);
        ListNode d = new ListNode(3);
        a.next = b;
        b.next = c;
        c.next = d;
        return a;
    }

    public static ListNode merge(ListNode left, ListNode right) {
        ListNode head;
        if (left.val < right.val) {
            head = left;
            left = left.next;
        } else {
            head = right;
            right = right.next;
        }

        ListNode cur = head;
        while (left != null && right != null) {
            if (left.val < right.val) {
                cur.next = left;
                left = left.next;
            } else {
                cur.next = right;
                right = right.next;
            }
            cur = cur.next;
        }

        if (left != null) {
            cur.next = left;
        } else {
            cur.next = right;
        }

        return head;
    }

    public static ListNode mergeSort(ListNode head, ListNode end) {
        if (head == null) return null;
        if (head.next == end) {
            head.next = null;
            return head;
        }

        ListNode fast = head;
        ListNode slow = head;

        while (fast != end) {
            slow = slow.next;
            fast = fast.next;
            if (fast != end) {
                fast = fast.next;
            }
        }

        ListNode mid = slow;
        ListNode left = mergeSort(head,mid);
        ListNode right = mergeSort(mid,end);
        ListNode ret = merge(left,right);

        return ret;
    }

    public static ListNode sortList(ListNode head) {
        return mergeSort(head,null);
    }

    public static void main5(String[] args) {
        ListNode root = creatList();
        sortList(root);
    }
    public static void main3(String[] args) {
        TreeNode root = creatTreeNode();
        TreeNode head = Convert(root);
        TreeNode cur = head;
        while (cur != null) {
            System.out.print(cur.val + " ");
            cur = cur.left;
        }
        System.out.println();
    }
    public static void main1(String[] args) {
        int[] ino = {9,3,15,20,7};
        int[] pos = {9,15,7,20,3};
        //buildTree(ino,pos);
    }
}
